《数据结构》

一、       试的基本要求

要求学生比较系统地理解数据结构的基本概念和基本理论，掌握各种数据结构特点、存储表示和常用算法，要求考生具有抽象思维能力、逻辑推断能力、空间想象能力、运算能力和综合运用所学知识分析问题和解决问题的能力。

二、考试方法和考试时间

数据结构为笔试，考试时间为1小时。

三、适用专业

数据结构考试试卷适用的专业为：工学类计算机科学与技术、电子科学与技术、信息与通讯工程等一级学科中所有的二级学科、专业。

四、考试内容及要求

（一）、线性表

1．  理解并掌握线性表的逻辑结构和顺序存储结构；

2．  掌握线性链表，循环链表，双向链表的链式存储结构及实现算法；

3．  掌握应用线性表来表示一元多项式且能实现一元多项式的相加。

（二）、栈和队列

1．  熟练掌握栈的定义、基本操作和实现算法；

2．  掌握应用栈来实现表达式求值；

3．  熟练掌握队列的定义、基本操作和实现算法；

4．  熟练掌握链式存储结构实现的链队列；

5．  熟练掌握顺序存储结构实现的循环队列。

（三）、串

1．  熟练掌握串的定义、逻辑结构及基本操作；

2．  掌握串的存储结构；

3．  掌握模式匹配的定义及基本算法。

（四）、数组和广义表

1．  掌握数组的定义和运算；

2．  熟练掌握数组的顺序存储结构及特殊矩阵的压缩存储；

3．  熟练掌握十字链表表示的稀疏矩阵；

4．  理解并掌握广义表的定义、存储结构。

（五）、树和二*树

1．  熟练掌握树的结构定义及基本操作；

2．  熟练掌握二*树的结构定义及基本操作；

3．  熟练掌握二*树的性质及存储结构；

4．  能熟练应用前序，中序，后序遍历及线索二*树；

5．  熟练掌握树的存储结构，树与二*树的相互转换、森林与二*树的相互转换，树的遍历算法；

6．  掌握哈夫曼树及其应用。

（六）、图

1．  熟练掌握图的定义和术语；

2．  熟练掌握图的邻接矩阵表示法，邻接表表示法；

3．  熟练掌握图的深度优先搜索和广度优先搜索算法；；

4．  理解生成树，最小生成树的概念；

5．  熟练掌握构造无向图的最小生成树的算法；

6．  熟练掌握拓扑排序和构造关键路径的算法；

7．  能快速求出从某个源点到其余各顶点的最短路径。

（七）、查找

1．  熟练掌握顺序查找，折半查找，分块查找的算法；

2．  掌握二*排序树，平衡二*树， B树的概念及相应的查找算法；

3．  了解哈希表的定义，哈希函数的构造方法及处理冲突的方法；

（八）、内部排序

1．  熟练掌握直接插入排序,希尔排序及算法；

2．  熟练掌握冒泡排序、快速排序及算法；

3．  熟练掌握简单选择排序及算法；

4．  了解二路归并排序的算法。

五、试卷结构

（一）、题型比例

填空题、选择题、判断题、简答题、计算或算法设计题

（二）、参考书目

《数据结构》，谈春媛、江红，电子工业出版社

《数据结构》，杨秀金，西安电子科技大学出版社